package 面试经典150题.滑动窗口;

import java.util.*;

//参考
//https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1054787/zen-yao-yong-hua-dong-chuang-kou-wei-he-35418/?envType=study-plan-v2&envId=top-interview-150
public class T3无重复字符的最长子串 {
    public static void main(String[] args) {
        String s = "pwwkew";
        int count = new T3无重复字符的最长子串().lengthOfLongestSubstring2(s);
        System.out.println(count);
    }

    //思路，滑动窗口
    //用set来构建一个滑动窗口，指针left和i的值是同步的，当把字符加进滑动窗口里面的时候
    //先判断 这个字符 是否在滑动窗口里面 在的话 就要把滑动窗口最左面的元素移除出去，然后继续判断
    //直到这个字符不在滑动窗口里面的时候，就把这个字符加入进滑动窗口里面
    //因为left和right的值都是从0开始的，所以计算长度就是temp=left-fight+1,
    //然后比较 temp和max的值 最大的就是子长度

    public int lengthOfLongestSubstring(String s) {
        int max = 0, right = 0, left = 0;
        char[] charArray = s.toCharArray();
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < charArray.length; i++) {
            while (set.contains(charArray[i])) {
                set.remove(charArray[left++]);
            }
            set.add(charArray[i]);
            int temp = right - left + 1;
            max = temp >= max ? temp : max;
            right++;
        }
        return max;
    }

    public int lengthOfLongestSubstring2(String s) {
        //滑动窗口解法，left和right分别是滑动窗口的左右区间，right和i同步
        int max = 0, left = 0, right = 0;
        Set<Character> set = new LinkedHashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //要用while循环判断这个字符在不在set里面
            while (set.contains(c)) {
                //在这个set里面的话，那么就把滑动窗口最左面的元素给移除掉
                set.remove(s.charAt(left));
                //把left往后面移动
                left++;
            }
            //不在set里面的话，就把这个c加入set
            set.add(c);
            //计算此时无重复字符串的长度 因为下标是从0开始的，所以长度最后还需要加上一个1
            int temp = right - left + 1;
            //更新最大长度max的值
            max = temp >= max ? temp : max;
            //right指针往后移动 如果right放在前面的话，就会是temp的结果偏大1个数
            right++;
        }
        //打印set里面的元素
        set.forEach(System.out::println);
        return max;
    }
}
